In a data communication network, a forwarding device (e.g., a data packet switch) directs protocol data units (e.g., data packets) from one network node to another. These data packets may include voice, video, or data information as well as any combination thereof.
To better understand how forwarding devices work within a data communication network, an analogy may be helpful. In many respects, data communication networks are similar to postal delivery systems, with pieces of mail, such as letters or packages, being comparable to the data packets which are transferred within a data communication network. In a postal delivery system, the pieces of mail may be input into the postal delivery system in a variety of ways. Once within the postal delivery system, all of the pieces of mail are collected and transported to nearby processing facilities where the pieces of mail are sorted for further processing. Although each piece of mail will have a unique delivery address, most of the pieces of mail are automatically sorted by a shorter zip code or some other type of routing code. Letters without zip codes must be sorted and processed by hand. Some postal delivery systems also have special forms of encoded delivery addresses, such as Post Office box numbers at a Post Office, which are not recognizable by other postal delivery systems such as Federal Express or United Parcel Service. Regardless of which particular postal delivery system the piece of mail is deposited into, once the mail has been sorted by destination it is routed through additional intermediary processing facilities until it arrives at the local indicated by the destination on the piece of mail. At this point, the zip code or routing code is no longer sufficient to deliver the piece of mail to the intended destination and the local delivery office must further decode the destination address in order to deliver the piece of mail to the intended recipient. In addition to processing pieces of mail for routing the mail to the correct destination, the pieces of mail may go on through several other processing steps. For example, if the piece of mail is going out of the country, it must go through a customs operation in each country. If the national postal delivery system is being used to deliver the piece of mail then it must also be transferred from one national postal delivery system to another. In a private postal delivery system however, this transfer step would not be necessary. The pieces of mail may also be monitored or filtered for such things as mail fraud violation or shipment of hazardous materials.
Data packets are manipulated in a data communication network in a manner similar to that by which pieces of mail are delivered in a postal delivery system. Data packets, for example, are generated by many different types of means and are placed onto a communication network. Typically, the data packets are concentrated into a forwarding device, such as a local bridge or router, and are then directed by size and destination over one or more media types (e.g., fiber optic) which are connected to further forwarding devices that could be other larger or smaller bridges or routers. These destination devices then deliver the data packet to its terminal end point (i.e., the end user). Along the way the data communication network may perform filtering and monitoring functions with respect to the data packets.
Just like postal delivery systems have experienced ever increasing volumes of mail which must be delivered, the volume of protocol data units being transferred across computer networks continues to increase as experience is being gained with this new form of communication delivery system and as more and more applications, with more and more expansive communications requirements are being developed. In addition, quickly changing technology has made the underlying data transmission resources for computer communication networks relatively inexpensive. Fiber optics, for example, offer data transfer rates in the gigabyte per second range.
One of the existing types of forwarding devices which offer the greatest potential to meet the increasing demand on throughput rates are packet switches. Several classes of packet switches exist. Each class differs substantially from the other class of devices, but all may be commonly referred to as packet switches or forwarding devices.
A first class of packet switches is that commonly used in digital telephone exchanges. By analogy, these switches can perform the functions only of a dedicated mail truck which relays mail between post offices and drops mail pouches on a post office loading dock. These switches are intended only to transfer packets among the devices in a single station, such as a telephone exchange, and are not capable of performing any sorting operations. The format of the packet in these systems is chosen to make the hardware in the switch as simple as possible; and this usually means that the packets include fields designed for direct use by the hardware. The capabilities of this class of switches (for example, in such areas as congestion control) are very limited in order to keep the hardware simple.
A second class of packet switches is used in smaller or restricted computer networks, such as X.25 networks. By analogy, these switches are equivalent to a group of #10 envelope sorters in the Post Office. These sorters handle and process this size envelope efficiently within the post office by performing limited sorting and routing functions, but can not by themselves deliver mail to its destination. In some sense, these switches are very different from the first class of packet switches described above, because several of this second class of packet switches can work together like several #10 envelope sorters can work at one time in the Post Office. However, there is one substantial similarity in that this second class of switches can only handle one format of packets (i.e., the protocols). The formats handled by the second class of packet switches is much more complex than those in the first class. This greater complexity is necessary because the protocols are designed to work in less restricted environments, and because the packet switches must provide a greater range of services. While the formats interpreted by the first class of switches are chosen for easy implementation in hardware, the data packets handled by this second class of switches are generally intended to be interpreted by software (which can easily and economically handle the greater complexity) and provides the inherit benefit of incremental flexibility in the design of the packet switch.
In a third class of packet switches, the packet protocols are intended to be used in very large data networks having many very dissimilar links (such as a mix of very high speed local area networks (LANs) and low speed long distance point to point lines). Examples of such protocols are the United States designed Transmission Control Protocol/Internet Protocol (TCP/IP), and the International Standards Organization's Connectionless Network Protocol (CLNP) protocols.
In addition, this third class of switches (commonly referred to as bridge/routers) often must handle multiple protocols simultaneously. This third class of switches is very similar to the mail processing devices used in the modern postal system. Just as there are many countries, there are many data packet protocols used in computer networks. While a single postal system was once thought to be sufficient to handle mail going anywhere in the world, today several competing systems like United Parcel Service, Federal Express, and the U.S. Postal Service exist to handle the special needs of mail going to every country, state, city, town, and street in the world. Similarly, in computer communication systems, the packet switches are more involved in the carrying of data, and must understand some of the details of each protocol to be able to correctly handle data packets which are being conveyed in that protocol. The routers in this third class of packet switches often have to make fairly complex changes to the data packets as they pass through the packet switch.
It is this latter class of packet switches to which the following detailed description primarily relates. It will be appreciated however, that the detailed description of this invention can readily be applied to the first and second class of switches as well.
In current conventional packet switch design, a programmed general purpose processor examines each data packet as it arrives over the network interface and then processes that packet. Packet processing requires assignment of the data packet to an outbound network interface for transmission over the next communications link in the data path.
Currently, most bridge/router implementations rely heavily on off-the-shelf microprocessors to perform the packet forwarding functions. The best implementations are able to sustain processing rates approaching 100,000 packets per second (PPS). When dealing with media such as Ethernet or current telecommunications lines, this processing rate is more than adequate. When faster media such as the Fiber Distributed Data Interface (FDDI) are used, existing processing rates may still be sufficient as long as there is only one such high packet rate interface present. When multiple high packet rate interfaces are used, 100,000 PPS become inadequate. Current software-based implementations for bridges/routers are simply not capable of media-rate packet forwarding on emerging media such as asynchronous transfer mode (ATM) or Optical Connection-12 Synchronous Optical Network (OC-12 SONET) which can accommodate communication rates up to 6 times the current 100 megabits per second limits to rates of 600 megabits per second. It should be noted that the ever increasing power of off-the-shelf microprocessors might solve the throughput problem, but this is probably a vain hope. For example, a single OC-24 ATM interface can sustain nearly 3 million internetworking protocol (IP) packets per second. This is over 30 times the rates achieved by the current best software techniques. If processing power doubles every year, the wait for sufficient processing power to make a software approach viable would be at least 4-5 years. In addition, the media capabilities will likely continue to increase over such a span of years. Additionally, any such processor will likely require large amounts of the fastest (most expensive) memory available to operate at full speed, resulting in an unacceptably high system cost.
Fortunately most individual packet switch customers will never require sustained packet transfer rates at these levels. However, the traditional approach of individual customers purchasing routers, bridges, modems, and leased phone lines is changing. A trend towards developing Metropolitan Area Networks (MANs) is beginning in the networking industry as an alternative to the traditional approach of individual customer local area networks (LANs) connected through customer owned leased telecommunication lines.
The more successful entrants in this area are capitalizing on three trends:
These MAN vendors are dealing with "customers" in the truest sense of the word, where customer and MAN vendor are independent enterprises. The trends towards corporate decentralization are even producing analogous situations within large enterprises.
Second, enterprises are becoming far more distributed than before, and the very definition of an "enterprise" is changing. Where in the 1980's all individuals involved in a program could be expected to reside in one or two well defined locations, a more modern "enterprise" may consist of individuals from several divisions, several corporations, consultants, roving sales and marketing people, and workers who want to telecommute at their convenience. At the same time, this modern enterprise needs to protect their information from disclosure or sabotage from without the group while preserving a liberal access policy from within.
A wide area "backbone" is a tremendous investment on the part of any large enterprise. Yet at the same time, host computers and small scale networks are becoming easier to administer while the expertise to administer them becomes more widespread. At the same time, organizations with a bias towards decentralization are seeing departments and divisions owning "their" hosts and "their" networks that they want to plug into a wide area backbone in order to carry their traffic. This traffic typically consists of communications to other divisions; however, increasingly it will also consist of traffic within a division with widely scattered sites.
All of this follows a known trend of increasing decentralization in the workplace. Many years ago, Management Information System (MIS) computers and all the networks in the enterprise. Access policy (such as was needed then) could largely be done through system administration of the host computers.
The advent of personal computers and affordable workstations meant that the networking administrators no longer owned all of the host computers anymore, yet these same MIS organizations are still charged with their traditional role of ensuring the integrity of the enterprise's data. This has led to the rise of routing and filtering functions within routers, making access control, a network, rather than a host problem.
Now the networking industry is moving up one more level. Today, clients not only own their own hosts, they own their own networks and want to connect these networks on a network to network basis. Yet at the same time, the need to preserve the integrity of data moving among client networks still exists. This trend is producing not just a "network", but a "network of networks", where the purpose of a backbone is to serve the needs and foibles of its constituent networks, not all of which may belong to the same enterprise.
The concept of a "network of networks" is not new. In fact, this was one of the guiding philosophies which led to the original creation of the Internet. Unfortunately, the logic to support this has only been applied to Internet Protocol and more recently to the Open Systems Interconnection (OSI) model. IP has been designed to perform this trick once (at the Internet level) and is little help in organizing traffic within a single IP network. Furthermore, IP cannot cope with the notion that a single network may be scattered at different points throughout the Internet.
Thus, a need exists for a way to provide equivalent protocols and management tools to those that exist today within a single network that will work in a "network of networks" paradigm.
One part of a solution to this problem is the use of Closed User Groups. A Closed User Group is a potentially widely distributed community of users and their associated networked computer equipment who permit free and open communications within the community, but severely restrict communication to points outside the community. The use of these Closed User Groups by MAN vendors is a means of addressing the trend that network topological or geographic proximity is becoming independent of access proximity. The general concept of a Closed User Group network environment is where data packets from different enterprises never interact with each other; however all of the data packets are carried across at least part of the network on the same shared media such an OC-12 data communications link. In a MAN environment that supports closed user groups, LAN's containing host computers are identified as belonging to a specific Closed User Group, and data packets for this LAN are transported to the desired location, then validated on receipt.
To better understand this concept let's refer once again to the postal service analogy. Several postal services need to send packages to the East coast of the United States on a regular basis. At first Federal Express, United Parcel Service, and the United States Postal Services all send these packages by separate airplanes, but a bright entrepreneur offers to build a special cargo plane that will carry all three sets of packages to the East coast in a single trip. All of the services like the idea, because it saves them operating expenses, but they want assurances that the none of the packages will get mixed with packages from other postal services. The entrepreneur agrees to divide the plane into three separate cargo areas so that no mixture of packages is possible. As a result, everyone is happy and the entrepreneur now has a thriving business. The MAN vendors are very similar to this entrepreneur and the postal services can be likened to individual companies or enterprises within the MAN's coverage area. Each MAN vendor provides these separate cargo areas by assigning each enterprise to a different Closed User Group. Thus, even though data from several enterprises are traveling on the same MAN shared medium data path, the data is separated by the Closed User Group assignments.
Although the user of Closed User Groups by MAN vendors offers a partial solution to the problems of "network of networks", there are no existing solutions for managing Closed User Groups that provide protocols and management tools equivalent to those now in use within a single network. A need still exists for an improved protocol data unit (i.e., frame, cell, or packet) forwarding system which solves the above-identified problems and promotes the use of the Closed User Group paradigm, while providing a wide variety of access control tools that permit network managers to assign users to a group or groups, and then define the policy of how those groups can interact within themselves and with each other.